package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/21 11:10 下午
 * <p>
 * https://leetcode-cn.com/problems/find-peak-element/
 * https://leetcode.wang/leetcode-162-Find-Peak-Element.html
 */
public class FindPeakElement {

    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 3, 1};

        FindPeakElement entity = new FindPeakElement();
        int ret = entity.findPeakElement(nums);


        System.out.println(ret);
    }

    /**
     * 因为 nums[-1]=负无穷  所以 遇到 nmus[i]>num[i+1]  肯定就是 峰值
     *
     * @param nums
     * @return
     */
    public int findPeakElement1(int[] nums) {

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }

        return nums.length - 1;
    }


    /**
     * 一般 logn   有序数组 我们才可以二分
     *
     * @param nums
     * @return
     */
    public int findPeakElement2(int[] nums) {

        int n = nums.length;

        if (n <= 1) {
            return n;
        }

        return findPeakElementHelper(0, nums.length - 1, nums);
    }


    public int findPeakElementHelper(int left, int right, int[] nums) {

        if (left == right) {
            return left;
        }

        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[mid + 1]) {
            //还在上升
            return findPeakElementHelper(left, mid, nums);
        } else {
            //还在上升
            return findPeakElementHelper(mid + 1, right, nums);
        }
    }


    /**
     * 一般 logn   有序数组 我们才可以二分
     *
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {

        int n = nums.length;

        if (n <= 1) {
            return n;
        }

        int left = 0;
        int right = n - 1;



        while (left != right) {

          int  mid = left + (right - left) / 2;

            if (nums[mid] <= nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

}
